package qjc.m_堆;

import java.util.HashMap;
import java.util.PriorityQueue;

public class m2_前K个高频元素 {
    /**
     * 通过哈希表保存，然后建立小顶堆
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) ->
                map.get(a) - map.get(b));
        for (int num : map.keySet()) {
            if (priorityQueue.size() < k) {
                priorityQueue.offer(num);
            } else if (map.get(num) > map.get(priorityQueue.peek())) {
                priorityQueue.poll();
                priorityQueue.offer(num);
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = priorityQueue.poll();
        }
        return res;
    }
}
